#include <iostream>

using namespace std;
// 25. K 个一组翻转链表
// 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* protect = new ListNode(0,head);   // 指向实际的head
        ListNode* last = protect;   // 前一组的尾结点
        // (1) 分组（往后走k-1步，找到一组）
        // 一组的开头head 结尾end
        while(head != nullptr) {
            ListNode* end = getEnd(head,k);
            if(end == nullptr) break;   // 不用分组

            ListNode* nextGroupHead = end->next;    // 下一组的开头
            // (2)一组内部(head到end之间)要翻转，调用（翻转链表）
            reverseList(head,nextGroupHead);
            // (3)更新每组跟前一组，后一组之间的边
            last->next = end;           // 和前一组连接
            head->next = nextGroupHead; // 和后一组连接

            // 维护上一组的last
            last = head;
            head = nextGroupHead;
        }
        return protect->next;
    }

private:
    // 返回向前走k-1步后的结点
    // 返回null，表示不够k个
    ListNode* getEnd(ListNode* head,int k) {
        while(head != nullptr) {
            k--;
            if(k == 0) return head;
            head = head->next;
        }
        return nullptr;
    }
    // 翻转从head到stop的链表，前闭后开区间
    void reverseList(ListNode* head, ListNode* stop) {
        ListNode* pre = head;
        head = head->next;  // 第一步跳过
        while (head != stop) {
            ListNode* next = head->next;

            head->next = pre;    // 翻转
            pre = head;
            head = next;
        }
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
